iT邦幫忙

2022 iThome 鐵人賽

DAY 12
0

前言

Call Stack,中文「呼叫堆疊」,是一個很重要的概念。這並不是Web相關技術中特有的,不過為了解釋後續的內容,我決定安插一節說一下Call Stack的概念。

Call Stack

Stack 是一個先進後出(First-In-Last-Out / FILO)的資料結構。就像一本本書疊起來,然後只能一本本從最上面開始拿下來。

image alt

Call Stack 就是每次函式呼叫,都會將函數的環境狀態保存進Stack,函數的環境狀態通常叫做「Call Frame」,而儲存Call Frame的Stack,就是Call Stack。

最明顯的例子就是遞歸函式,比如:

function sum(accum, end) {
  if (end === 0)
    return accum;
  return sum(accum + end, end -1);
}

sum(0, 5);

sum()是將 0 到 end 之間的整數累加起來,且end必須是大於等於0的整數。

當呼叫sum(0, 5)的時候,Call Stack便會儲存這筆資訊

| Call Stack |
| ---------- |
|            |
|            |
|            |
|            |
|            |
|            |
| sum(0, 5)  |
+------------+

由於sum(0, 5)回傳的是sum(5, 4)。但sum(5, 4)並不是直接的結果,同樣是一個函式呼叫,所以會在Call Stack多添加一筆Call Frame。

| Call Stack |
| ---------- |
|            |
|            |
|            |
|            |
|            |
| sum(5, 4)  |
| sum(0, 5)  |
+------------+

同樣的會直到sum(15, 0)

|  Call Stack |
| ----------- |
|             |
|  sum(15, 0) |
|  sum(14, 1) |
|  sum(12, 2) |
|  sum(9, 3)  |
|  sum(5, 4)  |
|  sum(0, 5)  |
+-------------+

但是sum(15, 0)的回傳值就是15,這並不是一個函式呼叫,因此可以直接將sum(15, 0)彈出。這邊先將結果記在Stack Top。

|  Call Stack |
| ----------- |
|             |
|     15      |
|  sum(14, 1) |
|  sum(12, 2) |
|  sum(9, 3)  |
|  sum(5, 4)  |
|  sum(0, 5)  |
+-------------+

然後可以一一將Call Frame彈出,最後可以得知sum(0, 5)的結果就是15

|  Call Stack |
| ----------- |
|             |
|             |
|             |
|             |
|             |
|     15      |
|  sum(0, 5)  |
+-------------+

基本上以上就是Call Stack的概念。也是呼叫函式時基本都會發生的,算是函式呼叫的固定成本。後續部分內容與這個概念有關。

本文同時發表於我的隨筆


上一篇
你可能不知道的即時更新方案:multipart/x-mixed-replace
下一篇
你可能不知道Array.prototype.forEach()沒跟你說的事情
系列文
這些那些你可能不知道我不知道的Web技術細節33
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言